package jago02.jago0201.ag02_lineTable;

import java.util.Arrays;
import java.util.Iterator;

/**
 * 顺序表
 * 杂化简：使用数组存储元素，存储数组元素的个数表示顺序表长度
 *
 * 解目录：
 *      1.用N表示线性表长度，线性表在数组中的范围为(0~N-1),线性表长度为N
 *      2.当N=数组长度时扩容，当N<数组长度/4时缩容
 *      3.数组长度伸缩方法就是创建新数组，将老数组内容复制到新数组
 *      4.自然添加元素到线性表就是将数据放到数组N位置后N++
 *      5.向线性表指定位置添加元素就是将指定位置元素全部后移一位，元素再放到指定位置后N++
 *      6.移除线性表指定位置元素就是将指定位置后的元素全部迁移一位，然后N--，并返回被删除元素
 *      7.查找元素在线性表位置索引，未找到则返回-1
 * 复杂度：查询O(1)，其他O(N)
 */
public class LineTable01_SequenceList<T> implements Iterable<T> {
    //元素数组
    private T[] eleArr;
    //线性表长度
    private int N;

    public LineTable01_SequenceList(int capacity) {
        this.eleArr = (T[])new Object[capacity];
        this.N = 0;
    }

    //置空线性表
    public void clear(){
        this.N = 0;
    }

    //判断线性表是否为空
    public boolean isEmpty(){
        return this.N == 0;
    }

    //获取线性表的长度
    public int length(){
        return this.N;
    }

    //自然的向线性表中添加一个元素t
    public void insert(T t){
        if (this.N == eleArr.length){
            //扩容
            resize(2*eleArr.length);
        }
        //插入数据
        eleArr[this.N++] = t;
    }

    //向线性表指定位置插入元素t
    public void insert(int index,T t){
        if (this.N == eleArr.length){
            //扩容
            resize(2*eleArr.length);
        }
        //将index处元素和其后面的元素全部后移一位
        for (int i = this.N; i >=index ; i--) {
            eleArr[i] = eleArr[i-1];
        }
        //将t放到index位置
        eleArr[index] = t;
        //线性表长度+1
        this.N++;
    }

    //删除指定位置元素
    public T remove(int index){
        if (this.N < eleArr.length/4){
            //缩容
            resize(eleArr.length/2);
        }
        T current = eleArr[index];
        //将index元素后的元素全部前移一位
        for (int i = index; i < this.N-1; i++) {
            eleArr[i] = eleArr[i+1];
        }
        //线性表长度-1
        this.N--;
        return current;
    }

    //查找首次出现元素t的位置,找不到则返回-1
    public int indexOf(T t){
        for (int i = 0; i < this.N; i++) {
            if (eleArr[i] == t){
                return i;
            }
        }
        return -1;
    }



    //动态伸缩数组长度
    private void resize(int newSize) {
        T[] temp = this.eleArr;
        this.eleArr = (T[])new Object[newSize];
        //复制原数组内容到新数组
        for (int i = 0; i < N; i++) {
            eleArr[i] = temp[i];
        }
    }

    private class SequenceListIterator implements Iterator{
        //当前元素
        private int cusor;

        public SequenceListIterator() {
            this.cusor = 0;
        }

        @Override
        public boolean hasNext() {
            return this.cusor < N;
        }

        @Override
        public Object next() {
            return eleArr[this.cusor++];
        }
    }

    @Override
    public Iterator iterator() {
        return new SequenceListIterator();
    }

    public static void main(String[] args) {
        LineTable01_SequenceList<String> sequenceList = new LineTable01_SequenceList(10);
        sequenceList.insert("张三");
        sequenceList.insert("李四");
        sequenceList.insert("王五");
        sequenceList.insert(1,"老朱");
        System.out.println(sequenceList);
        for (String str : sequenceList) {
            System.out.print(str+" ");
        }
    }

}
